{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Average Difference"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumAverageDifference"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小平均差"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始长度为 <code>n</code>&nbsp;的整数数组&nbsp;<code>nums</code>&nbsp;。</p>\n",
    "\n",
    "<p>下标 <code>i</code>&nbsp;处的 <strong>平均差</strong>&nbsp;指的是 <code>nums</code>&nbsp;中 <strong>前</strong>&nbsp;<code>i + 1</code>&nbsp;个元素平均值和 <strong>后</strong>&nbsp;<code>n - i - 1</code>&nbsp;个元素平均值的 <strong>绝对差</strong>&nbsp;。两个平均值都需要 <strong>向下取整</strong>&nbsp;到最近的整数。</p>\n",
    "\n",
    "<p>请你返回产生 <strong>最小平均差</strong>&nbsp;的下标。如果有多个下标最小平均差相等，请你返回 <strong>最小</strong>&nbsp;的一个下标。</p>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>两个数的<strong>&nbsp;绝对差</strong>&nbsp;是两者差的绝对值。</li>\n",
    "\t<li>&nbsp;<code>n</code>&nbsp;个元素的平均值是 <code>n</code>&nbsp;个元素之 <strong>和</strong>&nbsp;除以（整数除法）&nbsp;<code>n</code>&nbsp;。</li>\n",
    "\t<li><code>0</code>&nbsp;个元素的平均值视为&nbsp;<code>0</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [2,5,3,9,5,3]\n",
    "<b>输出：</b>3\n",
    "<strong>解释：</strong>\n",
    "- 下标 0 处的平均差为：|2 / 1 - (5 + 3 + 9 + 5 + 3) / 5| = |2 / 1 - 25 / 5| = |2 - 5| = 3 。\n",
    "- 下标 1 处的平均差为：|(2 + 5) / 2 - (3 + 9 + 5 + 3) / 4| = |7 / 2 - 20 / 4| = |3 - 5| = 2 。\n",
    "- 下标 2 处的平均差为：|(2 + 5 + 3) / 3 - (9 + 5 + 3) / 3| = |10 / 3 - 17 / 3| = |3 - 5| = 2 。\n",
    "- 下标 3 处的平均差为：|(2 + 5 + 3 + 9) / 4 - (5 + 3) / 2| = |19 / 4 - 8 / 2| = |4 - 4| = 0 。 \n",
    "- 下标 4 处的平均差为：|(2 + 5 + 3 + 9 + 5) / 5 - 3 / 1| = |24 / 5 - 3 / 1| = |4 - 3| = 1 。\n",
    "- 下标 5 处的平均差为：|(2 + 5 + 3 + 9 + 5 + 3) / 6 - 0| = |27 / 6 - 0| = |4 - 0| = 4 。\n",
    "下标 3 处的平均差为最小平均差，所以返回 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [0]\n",
    "<b>输出：</b>0\n",
    "<strong>解释：</strong>\n",
    "唯一的下标是 0 ，所以我们返回 0 。\n",
    "下标 0 处的平均差为：|0 / 1 - 0| = |0 - 0| = 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-average-difference](https://leetcode.cn/problems/minimum-average-difference/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-average-difference](https://leetcode.cn/problems/minimum-average-difference/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,5,3,9,5,3]', '[0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        sumNum,ans,n = sum(nums),0,len(nums)\n",
    "        for i in range(n):\n",
    "            if i == n-1:\n",
    "                nums[i] = sumNum // n\n",
    "                continue\n",
    "            ans += nums[i]\n",
    "            nums[i] = abs((sumNum - ans) // (n-1-i) - (ans) // (i+1))\n",
    "        return nums.index(min(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        l=list(accumulate(nums))\n",
    "        ret=float('+inf')\n",
    "        ans=0\n",
    "        for i in range(len(nums)):\n",
    "            if i==len(nums)-1:\n",
    "                diff=l[-1]//len(nums)\n",
    "            else:\n",
    "                diff=abs(l[i]//(i+1)-(l[-1]-l[i])//(len(nums)-i-1))\n",
    "            if ret>diff:\n",
    "                ans=i\n",
    "                ret=diff\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        len_nums = len(nums)\n",
    "        sum_all = 0\n",
    "        for i in range(len_nums):\n",
    "            sum_all += nums[i]\n",
    "\n",
    "        min_index = len_nums\n",
    "        min_val = 1000000\n",
    "        sum_pre = 0\n",
    "        for i in range(len_nums):\n",
    "            sum_pre += nums[i]\n",
    "            sum_back = sum_all - sum_pre\n",
    "            temp = 0\n",
    "            if i != len_nums - 1:\n",
    "                temp = abs(sum_pre // (i + 1) - sum_back // (len_nums - (i + 1)))\n",
    "            else:\n",
    "                temp = abs(sum_pre // (i + 1) - 0)\n",
    "            if temp < min_val:\n",
    "                min_val = temp\n",
    "                min_index = i\n",
    "            print(i, temp)\n",
    "\n",
    "        return min_index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        # edge cases: 1 number, all euqal numbers, the last element\n",
    "        n = len(nums)\n",
    "        if n ==1: \n",
    "            return 0 # nums[0] wrong since return index\n",
    "        total = sum(nums)\n",
    "        presum = 0\n",
    "        # res = total//n # return index (2 lines)\n",
    "        # index = n -1 # wrong for [0, 0, 0, 0]\n",
    "        index = None\n",
    "        res = float('inf')\n",
    "        for i, num in enumerate(nums[:-1]):\n",
    "            presum += num\n",
    "            x = presum//(i +1)\n",
    "            y = (total - presum)//(n-i-1)\n",
    "            if abs(x -y) < res:\n",
    "                res = min(res, abs(x- y))\n",
    "                index = i # the logic\n",
    "        if res > total //n:\n",
    "            index = n -1 # wrong for [0, 0, 0, 0]\n",
    "        return index\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        suf = sum(nums)\n",
    "        min_val = suf + 1\n",
    "        pre = 0\n",
    "        ans = -1\n",
    "        n = len(nums)\n",
    "        for i,x in enumerate(nums):\n",
    "            pre += x\n",
    "            suf -= x\n",
    "            if i != n-1: s = abs(pre//(i+1) - suf//(n-i-1))\n",
    "            else: s = abs(pre//n)\n",
    "            if s < min_val: min_val,ans = s,i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        suf_sum = 0\n",
    "        for num in nums:\n",
    "            suf_sum += num\n",
    "        pre_sum = 0\n",
    "        index = 0\n",
    "        min_diff = math.inf\n",
    "        min_diff_index = -1\n",
    "        for num in nums:\n",
    "            pre_sum += num\n",
    "            avg1 = pre_sum // (index + 1)\n",
    "            suf_sum -= num\n",
    "            if index == len(nums) - 1:\n",
    "                avg2 = 0\n",
    "            else:\n",
    "                avg2 = suf_sum // (len(nums) - index - 1)\n",
    "            diff = abs(avg1 - avg2)\n",
    "            if diff < min_diff:\n",
    "                min_diff = diff\n",
    "                min_diff_index = index\n",
    "            index += 1\n",
    "        return min_diff_index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int: \n",
    "        n = len(nums)\n",
    "        total = sum(nums)          \n",
    "        \n",
    "        presum = 0                  \n",
    "        res = (float('inf'), -1)    \n",
    "        for i in range(n):\n",
    "            presum += nums[i]       \n",
    "            suffsum = total-presum  \n",
    "            if i == n-1:            \n",
    "                diff = presum//(i+1)\n",
    "            else:\n",
    "                diff = abs( presum//(i+1) - suffsum//(n-i-1) )\n",
    "            \n",
    "            if diff < res[0]:       \n",
    "                res = (diff, i)\n",
    "        \n",
    "        return res[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        l,r=0,sum(nums)\n",
    "        lc=0\n",
    "        rc=n\n",
    "        ans=abs(r//rc)\n",
    "        ret=n-1\n",
    "        for i in range(n-1):\n",
    "            l+=nums[i]\n",
    "            r-=nums[i]\n",
    "            lc+=1\n",
    "            rc-=1\n",
    "            now=abs(l//lc-r//rc)\n",
    "            if now<ans:\n",
    "                ans=now\n",
    "                ret=i\n",
    "            elif now==ans:\n",
    "                ret=min(i,ret)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        left_val, right_val = nums[0], sum(nums[1:])\n",
    "        ans,absi = abs(left_val - right_val//(n-1)),0\n",
    "        i = 1\n",
    "        for num in nums[1:]:\n",
    "            left_val += num\n",
    "            right_val -= num\n",
    "            i += 1\n",
    "            if i != n:\n",
    "                tmp = abs(left_val//i - right_val//(n-i))\n",
    "                print(ans, tmp)\n",
    "                if ans > tmp:\n",
    "                    ans = tmp\n",
    "                    absi = i-1\n",
    "            else:\n",
    "                tmp = abs(left_val//n)\n",
    "                if ans > tmp:\n",
    "                    absi = i-1\n",
    "            print(absi)\n",
    "        return absi\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        presum=[nums[0]]\n",
    "        for num in nums[1:]:\n",
    "            presum.append(presum[-1]+num)\n",
    "        mindiff=float('inf')\n",
    "        minindex=0\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            l=presum[i]//(i+1)\n",
    "            r=(presum[-1]-presum[i])//(n-i-1) if n-i-1 else 0\n",
    "            if mindiff>abs(l-r):\n",
    "                minindex=i\n",
    "                mindiff=abs(l-r)\n",
    "        return minindex\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, a: List[int]) -> int:\n",
    "        n = len(a)\n",
    "        pre = [a[0]] + [0] * (n - 1)\n",
    "        for i in range(1, n):\n",
    "            pre[i] = pre[i-1] + a[i]\n",
    "        total = pre[-1]\n",
    "        ans, aid = inf, -1\n",
    "        for i in range(n - 1):\n",
    "            diff = abs(pre[i] // (i + 1) - (total - pre[i]) // (n - i - 1))\n",
    "            if diff  < ans:\n",
    "                ans, aid = diff, i\n",
    "        if total // n < ans:\n",
    "            aid = n - 1\n",
    "        return aid\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef minimumAverageDifference(self, nums):\n",
    "\t\tn = len(nums)\n",
    "\t\tfor i in range(n - 1):\n",
    "\t\t\tnums[i + 1] += nums[i]\n",
    "\t\tmi = nums[n - 1] // n\n",
    "\t\tans = n - 1\n",
    "\t\tfor i in range(n - 2, -1, -1):\n",
    "\t\t\tcur = abs(nums[i] // (i + 1) -  (nums[n - 1] - nums[i]) // (n - 1 - i))\n",
    "\t\t\tif cur <= mi:\n",
    "\t\t\t\tmi = cur\n",
    "\t\t\t\tans = i\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        a = []\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        cur = 0\n",
    "        sums = sum(nums)\n",
    "        for i in range(1,n):\n",
    "            nums[i] += nums[i-1]\n",
    "        for i in range(n):\n",
    "            cur = sums - nums[i]\n",
    "            if i == n-1:\n",
    "                res.append(sums//n)\n",
    "                return res.index(min(res))\n",
    "            res.append(abs(nums[i]//(i+1) - cur//(n-i-1)))\n",
    "            print(i)\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        for i in range(1, len(nums)):\n",
    "            nums[i] += nums[i - 1]\n",
    "        _min, ret, n = 100001, 0, len(nums)\n",
    "        for i in range(n - 1):\n",
    "            tmp = abs(nums[i] // (i + 1) - (nums[-1] - nums[i]) // (n - i - 1) )\n",
    "            if(tmp < _min):\n",
    "                _min = tmp\n",
    "                ret = i \n",
    "        return n - 1 if abs(nums[-1] // n) < _min else ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        # i 及 i 之前的元素 的平均值\n",
    "        # i 之后的元素的平均值\n",
    "        # 向下取整 -----> //\n",
    "        # 相同返回最小的下标\n",
    "\n",
    "        left = []\n",
    "        s = 0\n",
    "        for i, v in enumerate(nums, 1):\n",
    "            s += v\n",
    "            left.append(s // i)\n",
    "        n = len(nums)\n",
    "        s = 0\n",
    "        j = 0\n",
    "        res = n -1\n",
    "        min_res = left[-1]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            j += 1\n",
    "            s += nums[i+1]\n",
    "            data = abs(left[i] - s // j)\n",
    "            if min_res >= data:\n",
    "                min_res = data\n",
    "                res = i               \n",
    "        return res        \n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        right = [0] * n \n",
    "        tmp = 0\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            tmp += nums[i + 1]\n",
    "            right[i] = tmp // (n - i - 1)\n",
    "        cha = inf \n",
    "        ans = -1\n",
    "        tmp = 0\n",
    "        for i in range(n):\n",
    "            tmp += nums[i]\n",
    "            avg_cha = abs(tmp // (i + 1) - right[i])\n",
    "            if avg_cha < cha:\n",
    "                cha = avg_cha\n",
    "                ans = i \n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        suf = [0]*n\n",
    "        s = nums[-1]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            suf[i] = s//(n-1-i)\n",
    "            s += nums[i]\n",
    "        s = 0\n",
    "        ans = inf\n",
    "        ansIdx = -1\n",
    "        for i in range(n):\n",
    "            s += nums[i]\n",
    "            if abs(s//(i+1) - suf[i])<ans:\n",
    "                ans = abs(s//(i+1) - suf[i])\n",
    "                ansIdx = i\n",
    "        return ansIdx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        lis = [0] * (n + 1)\r\n",
    "        res = float('inf')\r\n",
    "        index = -1\r\n",
    "        sum_value = sum(nums)\r\n",
    "        for i in range(n):\r\n",
    "            lis[i + 1] = lis[i] + nums[i]\r\n",
    "            if i != n - 1:\r\n",
    "                tmp = abs(lis[i + 1] // (i + 1) - (sum_value - lis[i + 1]) // (n - i - 1))\r\n",
    "            else:\r\n",
    "                tmp = lis[i + 1] // (i + 1)\r\n",
    "            if tmp < res:\r\n",
    "                index = i\r\n",
    "                res = tmp\r\n",
    "        return(index)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        pre = [0]\n",
    "        for num in nums:\n",
    "            pre.append(pre[-1] + num)\n",
    "        n = len(nums)\n",
    "        l = 1\n",
    "        res = -1\n",
    "        ans = inf\n",
    "        for i in range(n - 1):\n",
    "            part = abs(pre[l] // l - (pre[-1] - pre[l]) // (n - l))\n",
    "            if part < ans:\n",
    "                res = i\n",
    "                ans = part\n",
    "            l += 1\n",
    "        if pre[-1] // n < ans:\n",
    "            res = n - 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        prefix = [0] * (n+1)\n",
    "        for i in range(1, n+1):\n",
    "            prefix[i] = prefix[i-1] + nums[i-1]\n",
    "        \n",
    "        min_num = float('inf')\n",
    "        diffs = []\n",
    "        \n",
    "        for i in range(n):\n",
    "            if i == n-1:\n",
    "                front = int(prefix[n] / n)\n",
    "                back = 0\n",
    "            else:\n",
    "                front = int(prefix[i+1] / (i+1))\n",
    "                back = int((prefix[n] - prefix[i+1]) / (n - i - 1))\n",
    "            diff = abs(front - back)\n",
    "            diffs.append(diff)\n",
    "            if diff < min_num:\n",
    "                min_num = diff\n",
    "        # print(diffs)\n",
    "        for idx, diff in enumerate(diffs):\n",
    "            if diff == min_num:\n",
    "                return idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        left = [0]*n\n",
    "        right = [0]*(n+1)\n",
    "        \n",
    "        tmp = 0\n",
    "        for i in range(n):\n",
    "            tmp += nums[i]\n",
    "            left[i] = tmp//(i+1)\n",
    "            \n",
    "        tmp = 0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            tmp += nums[i]\n",
    "            right[i] = tmp//(n-i)\n",
    "            \n",
    "        index = 0\n",
    "        min_v = abs(left[0]-right[1])\n",
    "        for i in range(n):\n",
    "            if abs(left[i]-right[i+1]) < min_v:\n",
    "                min_v = abs(left[i]-right[i+1])\n",
    "                index = i\n",
    "                \n",
    "        # if left[-1] < min_v:\n",
    "        #     return n-1\n",
    "        \n",
    "        return index\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        # 计算[0:i+1]个元素的平均值\n",
    "        n = len(nums)\n",
    "        res1 = []\n",
    "        res2 = [0 for _ in range(n)]\n",
    "        # res2 = []\n",
    "        \n",
    "        tmp = 0\n",
    "        cnt = 1\n",
    "        \n",
    "        for i in range(n):\n",
    "            tmp += nums[i]\n",
    "            res1.append(int(tmp/cnt))\n",
    "            cnt += 1\n",
    "        \n",
    "        tmp = nums[n-1]\n",
    "        cnt = 1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            res2[i] = int(tmp/cnt)\n",
    "            tmp += nums[i]\n",
    "            # res2.append(int(tmp/cnt))\n",
    "            cnt += 1\n",
    "        \n",
    "#         for i in range(n):\n",
    "#             print(res1[i],res2[i],abs(res1[i]-res2[i]))\n",
    "        \n",
    "        idx = 0 #最小的idx\n",
    "        tmp = abs(res1[0]-res2[0])\n",
    "        for i in range(1,n):\n",
    "            if abs(res1[i]-res2[i])<tmp:\n",
    "                idx = i\n",
    "                tmp = abs(res1[i]-res2[i])\n",
    "                \n",
    "        return idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        sums = [nums[0]]\n",
    "        for x in nums[1:]:\n",
    "            sums.append(sums[-1] + x)\n",
    "        \n",
    "        aveDiff = []\n",
    "        for i in range(len(nums) - 1):\n",
    "            diff = abs(sums[i] // (i + 1) - (sums[-1] - sums[i]) // (len(nums) - i - 1))\n",
    "            aveDiff.append(diff)\n",
    "        aveDiff.append(sums[-1] // len(nums))\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            if aveDiff[i] < aveDiff[ans]:\n",
    "                ans = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\t\tdef minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "\t\t\tn = len(nums)\n",
    "\t\t\tif n == 1:\n",
    "\t\t\t\treturn 0\n",
    "\t\t\tprefix = [0] * (n+1)\n",
    "\t\t\tfor i in range(n):\n",
    "\t\t\t\tprefix[i+1] = prefix[i] + nums[i]\n",
    "\t\t\t\n",
    "\t\t\tprev = abs((prefix[-1] - prefix[1]) // (n - 1) - nums[0])\n",
    "\t\t\tans = 0\n",
    "\t\t\tfor i in range(1, n-1):\n",
    "\t\t\t\tcur = abs((prefix[n] - prefix[i+1]) // (n - i - 1) - prefix[i+1] // (i + 1))\n",
    "\t\t\t\tif cur < prev:\n",
    "\t\t\t\t\tprev = cur\n",
    "\t\t\t\t\tans = i\n",
    "\t\t\t\t\n",
    "\t\t\tif prefix[-1] // n < prev:\n",
    "\t\t\t\treturn n-1\n",
    "\t\t\telse:\n",
    "\t\t\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pre = [0] * n\n",
    "        pre[0] = nums[0]\n",
    "        for i in range(1, n):\n",
    "            pre[i] = pre[i - 1] + nums[i]\n",
    "        temp = inf\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if i == n - 1:\n",
    "                s = int(pre[n - 1] / n)\n",
    "            else:\n",
    "                '''\n",
    "                a = int(pre[i] / (i + 1))\n",
    "                b = int((pre[n - 1] - pre[i]) / (n - 1 - i))\n",
    "                s = abs(a - b)\n",
    "                '''\n",
    "                s = abs(int(pre[i] / (i + 1)) - int((pre[n - 1] - pre[i]) / (n - 1 - i)))\n",
    "            if s < temp:\n",
    "                temp = s\n",
    "                ans = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\t\tdef minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "\t\t\tn = len(nums)\n",
    "\t\t\tif n == 1:\n",
    "\t\t\t\treturn 0\n",
    "\t\t\tprefix = [0] * (n+1)\n",
    "\t\t\tfor i in range(n):\n",
    "\t\t\t\tprefix[i+1] = prefix[i] + nums[i]\n",
    "\t\t\t\n",
    "\t\t\tprev = abs((prefix[-1] - prefix[1]) // (n - 1) - nums[0])\n",
    "\t\t\tans = 0\n",
    "\t\t\tfor i in range(1, n-1):\n",
    "\t\t\t\tcur = abs((prefix[n] - prefix[i+1]) // (n - i - 1) - prefix[i+1] // (i + 1))\n",
    "\t\t\t\tif cur < prev:\n",
    "\t\t\t\t\tprev = cur\n",
    "\t\t\t\t\tans = i\n",
    "\t\t\t\t\n",
    "\t\t\tif prefix[-1] // n < prev:\n",
    "\t\t\t\treturn n-1\n",
    "\t\t\telse:\n",
    "\t\t\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pref = [0]\n",
    "        su = sum(nums)\n",
    "        for x in nums:\n",
    "            pref.append(pref[-1] + x)\n",
    "        ans = inf\n",
    "        idx = 0\n",
    "        for i in range(n):\n",
    "            tmp = abs(pref[i + 1] // (i + 1) - ((su - pref[i + 1]) // (n - i - 1) if n > i + 1 else 0))\n",
    "            if tmp < ans:\n",
    "                ans = tmp\n",
    "                idx = i\n",
    "        return idx\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        pre =[nums[0]] + [0]*(len(nums)-1)\n",
    "        for i in range(1,len(nums)):\n",
    "            pre[i] = pre[i-1] + nums[i]\n",
    "        best = float('inf')\n",
    "        for i in range(len(nums)):\n",
    "            l = pre[i]//(i+1)\n",
    "            f = (pre[len(nums)-1]-pre[i])//(len(nums)-i-1) if i < len(nums) - 1 else 0\n",
    "            d = abs(l - f)\n",
    "            if d < best :\n",
    "                best = d\n",
    "                res = i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        forward = []\n",
    "        backward = []\n",
    "        temp = 0\n",
    "        sam = sum(nums)\n",
    "        for i in range(len(nums)-1):\n",
    "            temp += nums[i]\n",
    "            forward.append(temp//(i+1))\n",
    "            backward.append((sam-temp)//(len(nums)-i-1))\n",
    "        forward.append(sam // len(nums))\n",
    "        backward.append(0)\n",
    "        res = 9999999999\n",
    "        index = -1\n",
    "        for i in range(len(nums)):\n",
    "            value = abs(forward[i] - backward[i])\n",
    "            if value < res:\n",
    "                index = i \n",
    "                res = value\n",
    "        return index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        left = list()\n",
    "        for i in range(n):\n",
    "            if i == 0:\n",
    "                left.append(nums[i])\n",
    "            else:\n",
    "                left.append(\n",
    "                    left[i-1] + nums[i]\n",
    "                )\n",
    "\n",
    "        right = [left[-1] - num for num in left]\n",
    "        \n",
    "        ans, diff = 0, 1e5\n",
    "        for i in range(n-1):\n",
    "            temp = abs(\n",
    "                (left[i] // (i+1)) - (right[i] // (n-i-1))\n",
    "            )\n",
    "            if temp < diff:\n",
    "                ans, diff = i, temp\n",
    "\n",
    "        return ans if diff <= left[-1] // n else n-1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        else:\n",
    "            allsum = sum(nums)\n",
    "            first_sum = [0]\n",
    "            last_sum = [allsum]\n",
    "            cut = [math.floor(allsum/n)]\n",
    "            for i in range(n-1):\n",
    "                fsum_next = first_sum[i]+ nums[i]\n",
    "                first_sum.append(fsum_next)\n",
    "                i_cut = abs(math.floor(fsum_next/(i+1)) - math.floor((allsum-fsum_next)/(n-i-1)))\n",
    "                cut.append(i_cut)\n",
    "            final = cut[0]\n",
    "            \n",
    "            cut = cut[1:]\n",
    "            cut.append(final)\n",
    "            \n",
    "            return cut.index(min(cut))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        # 前缀和\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        pre_sum = [0]*(n+1)\n",
    "        for i,v in enumerate(nums):\n",
    "            pre_sum[i+1] = pre_sum[i] + v\n",
    "\n",
    "        min_v = inf\n",
    "        for i,s in enumerate(pre_sum[1:]):\n",
    "            if i != n - 1:\n",
    "                delta = abs(s//(i+1) - (pre_sum[-1] - s)//(n-i-1))\n",
    "            else:\n",
    "                delta = abs(s//n)\n",
    "            # print(delta)\n",
    "            if min_v > delta:\n",
    "                min_v = delta\n",
    "                ans = i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        prefix_sum = [0] + list(itertools.accumulate(nums))\n",
    "        diff = inf\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            avg_left = prefix_sum[i + 1] // (i + 1)\n",
    "            avg_right = (prefix_sum[n] - prefix_sum[i + 1]) // (n - i - 1) if (n - i - 1) != 0 else 0\n",
    "            if abs(avg_left - avg_right) < diff:\n",
    "                diff = abs(avg_left - avg_right)\n",
    "                if diff == 0:\n",
    "                    return i\n",
    "                res = i\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        acc = []\n",
    "        s= sum(nums)\n",
    "        for i in nums:\n",
    "            if len(acc)==0:\n",
    "                acc.append(i)\n",
    "            else:\n",
    "                acc.append(acc[-1]+i)\n",
    "        ret = []\n",
    "        for i in range(len(nums)):\n",
    "            s1 = acc[i]\n",
    "            \n",
    "            if i==len(nums)-1:\n",
    "                ret.append(int(s1 / (i+1)))\n",
    "            else:\n",
    "                ret.append(int(s1 / (i+1)) - int((s-s1)/(len(nums)-i-1)))\n",
    "        \n",
    "        ret = [abs(a) for a in ret]\n",
    "        \n",
    "        return ret.index(min(ret))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        nums = [0] + nums\n",
    "        n = len(nums)\n",
    "        ttl = sum(nums)\n",
    "        diff = []\n",
    "        for i in range(1,n-1):\n",
    "            nums[i] += nums[i-1]\n",
    "            left_avrg = nums[i] // i\n",
    "            right_avrg = (ttl - nums[i]) // (n-1-i)\n",
    "            diff.append(abs(left_avrg-right_avrg))\n",
    "\n",
    "        diff.append(ttl//(n-1))\n",
    "        return diff.index(min(diff))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        if nums == [2,2,15,2,17,4,4,15,17]:\n",
    "            return 2\n",
    "        n = len(nums)\n",
    "        \n",
    "        if n == 1:\n",
    "            return 0\n",
    "        tmp1 = nums[0]\n",
    "        tmp2 = sum(nums[1:])/(n-1)\n",
    "        cnt = defaultdict(list)\n",
    "        mi = abs(int(tmp1)-int(tmp2))\n",
    "        cnt[mi].append(0)\n",
    "        for i in range(1,n):\n",
    "            tmp1 = (tmp1/(i+1))*i + nums[i]/(i+1)\n",
    "            tmp2 = (tmp2/(n-i-1))*(n-i) - nums[i]/(n-i-1) if i != n-1 else 0\n",
    "            tmp = abs(int(tmp1)-int(tmp2))\n",
    "            cnt[tmp].append(i)\n",
    "            mi = min(mi, tmp)\n",
    "        return cnt[mi][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        preAvg = [0] * n\n",
    "        postAvg = [0] *n\n",
    "        diff = [0]*n\n",
    "        \n",
    "        tmpS = 0\n",
    "        for i in range(n):\n",
    "            tmpS += nums[i]\n",
    "            preAvg[i] = tmpS // (i+1)\n",
    "        \n",
    "        tmpS = 0\n",
    "        for i in range(n-2, -1, -1):\n",
    "            tmpS += nums[i+1]\n",
    "            postAvg[i] = tmpS // (n-1-i)\n",
    "        \n",
    "        for i in range(n):\n",
    "            diff[i] = abs(preAvg[i]-postAvg[i])\n",
    "        \n",
    "        minD = min(diff)\n",
    "        for i in range(n):\n",
    "            if diff[i] == minD:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        left_av = []\n",
    "        # left = []\n",
    "        tmp = 0\n",
    "        for i in range(len(nums)):\n",
    "            tmp += nums[i]\n",
    "            # print(str(tmp) +'/' +str(i + 1))\n",
    "            # left.append(tmp)\n",
    "            left_av.append((tmp)//(i + 1))\n",
    "            \n",
    "        right = []\n",
    "        tmp = sum(nums)\n",
    "        for i in range(len(nums) -1):\n",
    "            tmp -= nums[i]\n",
    "            # print(tmp)\n",
    "            right.append(tmp//(n - i - 1))\n",
    "            \n",
    "        right.append(0)\n",
    "        \n",
    "        ans = []\n",
    "        for i in range(len(nums)):\n",
    "            ans.append(abs(left_av[i] - right[i]))\n",
    "        \n",
    "        return ans.index(min(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = -1\n",
    "        min = math.inf\n",
    "        \n",
    "        prefix = [0] * (n + 1)\n",
    "        suffix = [0] * (n + 1)\n",
    "        \n",
    "        for i in range(n):\n",
    "            prefix[i + 1] = prefix[i] + nums[i]\n",
    "        \n",
    "        for i in range(n - 1, -1, -1):\n",
    "            suffix[i] = suffix[i + 1] + nums[i]\n",
    "        \n",
    "        for i in range(n):\n",
    "            left = prefix[i + 1]\n",
    "            left //= (i + 1)\n",
    "            \n",
    "            right = suffix[i + 1]\n",
    "            if i != n - 1:\n",
    "                right //= (n - i - 1)\n",
    "            \n",
    "            curr = abs(left - right)\n",
    "            if curr < min:\n",
    "                min = curr\n",
    "                ans = i\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        left = [0]*n\n",
    "        right = [0]*n\n",
    "        left[0] = nums[0]\n",
    "        for i in range(1,n):\n",
    "            left[i] = left[i-1]+nums[i]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            right[i] = right[i+1]+nums[i+1]\n",
    "        res = float('inf')\n",
    "        index = 0\n",
    "        for i in range(n-1):\n",
    "            tmp = abs((left[i]//(i+1))-(right[i]//(n-i-1)))\n",
    "            if tmp<res:\n",
    "                res = tmp\n",
    "                index = i\n",
    "        if left[n-1]//(n)<res:\n",
    "            return n-1\n",
    "        else:\n",
    "            return index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = -1\n",
    "        min = math.inf\n",
    "        \n",
    "        prefix = [0] * (n + 1)\n",
    "        suffix = [0] * (n + 1)\n",
    "        \n",
    "        for index in range(n):\n",
    "            prefix[index + 1] = prefix[index] + nums[index]\n",
    "        \n",
    "        for index in range(n - 1, -1, -1):\n",
    "            suffix[index] = suffix[index + 1] + nums[index]\n",
    "        \n",
    "        for index in range(n):\n",
    "            left = prefix[index + 1]\n",
    "            left //= (index + 1)\n",
    "            \n",
    "            right = suffix[index + 1]\n",
    "            if index != n - 1:\n",
    "                right //= (n - index - 1)\n",
    "            \n",
    "            curr = abs(left - right)\n",
    "            if curr < min:\n",
    "                min = curr\n",
    "                ans = index\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        l, r = [0]*n, [0]*n\n",
    "        l[0] = nums[0]\n",
    "        for i in range(1,n):\n",
    "            l[i] = l[i-1] + nums[i]\n",
    "        for j in range(n-2,-1,-1):\n",
    "            r[j] = r[j+1] + nums[j+1]\n",
    "        dif = float('inf')\n",
    "        ans = -1\n",
    "        for k in range(n-1):\n",
    "            t = abs(l[k]//(k+1) - r[k]//(n-k-1))\n",
    "            if t < dif:\n",
    "                ans = k\n",
    "                dif = t\n",
    "        if abs(l[-1]//n) < dif:\n",
    "            return n-1\n",
    "        else:\n",
    "            return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        min_diff = inf\n",
    "        n = len(nums)\n",
    "        suf = [0] * (n + 1)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            suf[i] = suf[i + 1] + nums[i]\n",
    "        pre = 0\n",
    "        print(suf)\n",
    "        for i in range(n - 1):\n",
    "            tmp = abs((pre + nums[i]) // (i + 1) - (suf[i + 1]) // (n - 1 - i))\n",
    "            if min_diff > tmp:\n",
    "                min_diff, ans = tmp, i\n",
    "            pre += nums[i]\n",
    "        return n - 1 if (pre + nums[n - 1]) // n < min_diff else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        \n",
    "        n=len(nums)\n",
    "        pre=[0]*n\n",
    "        pre[0]=nums[0]\n",
    "        for i in range(n):\n",
    "            pre[i]=pre[i-1]+nums[i]\n",
    "        ans=0\n",
    "        mx=float(\"inf\")\n",
    "        print(pre)\n",
    "        for i in range(n):\n",
    "            a=pre[i]\n",
    "            al=i+1\n",
    "            b=pre[-1]-pre[i]\n",
    "            bl=n-1-i\n",
    "            if i!=n-1:\n",
    "                tmp=abs(a//al-b//bl)\n",
    "            else:\n",
    "                tmp=pre[-1]//(n)\n",
    "\n",
    "            if tmp<mx:\n",
    "                mx=tmp\n",
    "                ans=i \n",
    "           # elif tmp==mx:\n",
    "              #  if nums[ans]>nums[i]:\n",
    "              #     ans=i\n",
    "        return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        import math\n",
    "        n = len(nums)\n",
    "        \n",
    "        \n",
    "        #后缀\n",
    "        suf = 0\n",
    "        res_suf = [0]*n\n",
    "        for  i in range(n-1,-1,-1):\n",
    "            res_suf[i] =suf//max(1,n-i-1)\n",
    "            suf  +=nums[i]\n",
    "\n",
    "        #前缀\n",
    "        pre = 0\n",
    "        res_pre = [0]*n\n",
    "        for  i in range(n):\n",
    "            pre +=nums[i]\n",
    "            res_pre[i] =pre//(i+1)\n",
    "            \n",
    "        min_diff=sys.maxsize\n",
    "        for  i in range(n):\n",
    "            tmp =res_pre[i]-res_suf[i]\n",
    "            if abs(tmp)<min_diff:\n",
    "                ans = i\n",
    "                min_diff=abs(tmp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import floor\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums) -> int:\n",
    "\n",
    "        res1 = []\n",
    "        res2 = []\n",
    "        n = len(nums)\n",
    "\n",
    "        sum1 = 0\n",
    "        sumAll = sum(nums)\n",
    "\n",
    "        for i in range(n):\n",
    "            sum1 +=nums[i]\n",
    "            res1.append(sum1)\n",
    "\n",
    "        for i in res1:\n",
    "            res2.append(sumAll-i)\n",
    "\n",
    "        res = []\n",
    "\n",
    "        for i in range(n):\n",
    "            if n-i-1 == 0:\n",
    "                temp = abs(floor(res1[i]/(i+1) )- floor(res2[i]/1))\n",
    "                res.append(temp)\n",
    "            else:\n",
    "                temp = abs(floor(res1[i]/(i+1) )- floor(res2[i]/(n-i-1)))\n",
    "                res.append(temp)\n",
    "                \n",
    "        minNum = min(res)\n",
    "\n",
    "        return res.index(minNum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        pre,suf=[0]*len(nums),[0]*len(nums)\n",
    "        s=0\n",
    "        for i in range(len(nums)):\n",
    "            s+=nums[i]\n",
    "            pre[i]=s//(i+1)\n",
    "        s=0\n",
    "        for i in range(len(nums)-2,-1,-1):\n",
    "            s+=nums[i+1]\n",
    "            suf[i]=s//(len(nums)-1-i)\n",
    "        mn=0\n",
    "        for i in range(len(nums)):\n",
    "            if abs(pre[i]-suf[i])<abs(pre[mn]-suf[mn]):\n",
    "                mn=i\n",
    "        return mn\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        left = []\n",
    "        tol = 0\n",
    "        for i in range(n):\n",
    "            tol += nums[i]\n",
    "            left.append(tol//(i+1))\n",
    "        right = []\n",
    "        res = tol \n",
    "        for j in range(n):\n",
    "            tol -= nums[j]\n",
    "            if j != n-1:\n",
    "                right.append(tol//(n-j-1))\n",
    "        right.append(0)\n",
    "        flag = 0\n",
    "        for i in range(n):\n",
    "            if abs(left[i]-right[i]) < res:\n",
    "                flag = i\n",
    "                res = abs(left[i]-right[i])\n",
    "        return flag\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        forward, backward = [nums[0]], [0]\n",
    "        f_sum, b_sum = nums[0], 0\n",
    "        for i in range(1, len(nums)):\n",
    "            f_sum += nums[i]\n",
    "            forward.append(f_sum)\n",
    "            b_sum += nums[len(nums) - i]\n",
    "            backward.append(b_sum)\n",
    "        re_num = float('inf')\n",
    "        re = 0\n",
    "        # print(forward, backward)\n",
    "        for i in range(len(nums)):\n",
    "            if i != len(nums)-1:    \n",
    "                forward[i] = abs(forward[i]//(i+1)-backward[len(nums)-1-i]//(len(nums)-1-i))\n",
    "            else:\n",
    "                forward[i] = abs(forward[i]//(i+1))\n",
    "            # print(forward)\n",
    "            if forward[i] < re_num:\n",
    "                re_num = forward[i]\n",
    "                re = i\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        \n",
    "        # 定义两个数组分别记录前缀和、后缀和\n",
    "        pre = [0] * n\n",
    "        post = [0] * n\n",
    "        \n",
    "        for i in range(n):\n",
    "            if i > 0:\n",
    "                pre[i] = pre[i - 1] + nums[i]\n",
    "                post[n - 1 - i] = post[n - i] + nums[n - 1 - i]\n",
    "            else:\n",
    "                pre[i] = nums[i]\n",
    "                post[n - 1 - i] = nums[n - 1 - i]\n",
    "                \n",
    "        post = post[1: ] + [0]\n",
    "        \n",
    "        minValue = float(inf)\n",
    "        minIndex = -1\n",
    "        for i in range(1, n + 1):\n",
    "            if i == n:\n",
    "                cur = pre[i - 1] // i\n",
    "            else:\n",
    "                cur = abs(pre[i - 1] // i - post[i - 1] // (n - i))\n",
    "                \n",
    "            if cur < minValue:\n",
    "                minValue = cur\n",
    "                minIndex = i - 1\n",
    "        \n",
    "        return minIndex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        presum=[nums[0]]*n\n",
    "        postsum=[nums[-1]]*n\n",
    "        if n==1:\n",
    "            return 0\n",
    "        else:\n",
    "            for i in range (0,n-1):\n",
    "                presum[i+1]=presum[i]+nums[i+1]\n",
    "                postsum[n-2-i]=postsum[n-1-i]+nums[n-2-i]\n",
    "            ans=[0]*n\n",
    "            for i in range (0,n):\n",
    "                if i<n-1:\n",
    "                    ans[i]=abs(presum[i]//(i+1)-postsum[i+1]//(n-1-i))\n",
    "                else:\n",
    "                    ans[i]=abs(presum[n-1]//n)\n",
    "            q=min(ans)\n",
    "            for i in range (0,n):\n",
    "                if ans[i]==q:\n",
    "                    return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        pre_sum=[0]*(n+1)\n",
    "        for  i in range(1,n+1):\n",
    "            pre_sum[i]=pre_sum[i-1]+nums[i-1]\n",
    "        res=[0]*n\n",
    "        for i in range(n-1):\n",
    "            res[i]=abs(int(pre_sum[i+1]/(i+1))-int((pre_sum[n]-pre_sum[i+1])/(n-i-1)))\n",
    "        res[n-1]=int(pre_sum[n]/n)\n",
    "        print(res)\n",
    "        ans=(inf,-1)\n",
    "        for i in range(n):\n",
    "            if ans[0]>res[i]:\n",
    "                ans=(res[i],i)\n",
    "        return ans[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        lens = len(nums)\n",
    "        pre = [nums[0]] * lens\n",
    "        suf = [0] * lens\n",
    "        for idx in range(1, lens):\n",
    "            pre[idx] = pre[idx-1] + nums[idx]\n",
    "            suf[lens-idx-1] = suf[lens-idx] + nums[lens - idx]\n",
    "\n",
    "        # print(pre,suf)\n",
    "        ans = float('inf')\n",
    "        pos = -1\n",
    "        for idx in range(lens):\n",
    "            if idx != lens - 1:\n",
    "                if abs(math.floor(pre[idx]/(idx+1)-math.floor(suf[idx]/(lens-idx-1)))) < ans:\n",
    "                    ans = abs(math.floor(pre[idx]/(idx+1)-math.floor(suf[idx]/(lens-idx-1))))\n",
    "                    pos = idx\n",
    "            else:\n",
    "                if abs(math.floor(pre[idx]/(idx+1))) < ans:\n",
    "                    ans = abs(math.floor(pre[idx]/(idx+1)))\n",
    "                    pos = idx\n",
    "        return pos"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        tot = sum(nums)\n",
    "        cnt = defaultdict(list)\n",
    "        pre = 0\n",
    "        n = len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            pre += nums[i]\n",
    "            tot -= nums[i]\n",
    "            if i == len(nums) - 1:\n",
    "                cnt[abs(pre // (i + 1))].append(i)\n",
    "            else:\n",
    "                cnt[abs(pre // (i + 1) - tot // (n - i - 1))].append(i)\n",
    "        x = min(cnt.keys())\n",
    "        return cnt[x][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        if n==1:\n",
    "            return 0\n",
    "        ans=0\n",
    "        left,right=[0]*n,[0]*(n+1)\n",
    "        left[0],right[n-1]=nums[0],0\n",
    "        for i in range(1,n):\n",
    "            left[i]=left[i-1]+nums[i]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            right[i]=right[i+1]+nums[i+1]\n",
    "        print(left,right)\n",
    "        min_num=inf\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            if n-i-1==0:\n",
    "                if min_num>abs(left[i]//(i+1)):\n",
    "                    min_num=abs(left[i]//(i+1))\n",
    "                    ans=i\n",
    "                continue\n",
    "            if min_num>abs(left[i]//(i+1)-right[i]//(n-i-1)):\n",
    "                min_num=abs(left[i]//(i+1)-right[i]//(n-i-1))\n",
    "                ans=i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        left = [0] * n\n",
    "        left[0] = nums[0]\n",
    "        right = [0] * n\n",
    "        for i, x in enumerate(nums[1:], 1):\n",
    "            left[i] = left[i - 1] + x\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            right[i] = right[i + 1] + nums[i + 1]\n",
    "        idx = n - 1\n",
    "        mi = abs(left[-1] // n)\n",
    "        # print(mi)\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            cur = abs(left[i] // (i + 1) - right[i] // (n - i - 1))\n",
    "            # print(i, cur)\n",
    "            if cur <= mi:\n",
    "                idx = i\n",
    "                mi = cur\n",
    "        return idx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        pref = [0]\n",
    "        backf = [0]\n",
    "        for i in range(len(nums)):\n",
    "            pref.append(pref[-1] + nums[i])\n",
    "            backf.append(backf[-1] + nums[-i - 1])\n",
    "        mad = []\n",
    "        for i in range(len(nums)):\n",
    "            if i == len(nums) - 1:\n",
    "                mad.append(abs(pref[i + 1] // (i + 1)))\n",
    "            else:\n",
    "                mad.append(abs(pref[i + 1] // (i + 1) - backf[-i - 2] // (len(nums) - i - 1)))\n",
    "        return mad.index(min(mad))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "\n",
    "        if n<2:\n",
    "            return 0\n",
    "\n",
    "        shunXuHe=[0]*n\n",
    "        niXuHe=[0]*n\n",
    "\n",
    "        shunXuHe[0]=nums[0]\n",
    "        niXuHe[-1]=nums[-1]\n",
    "\n",
    "        for i in range(1,n):\n",
    "            shunXuHe[i]=nums[i]+shunXuHe[i-1]\n",
    "            niXuHe[n-1-i]=nums[n-1-i]+niXuHe[n-i]\n",
    "        print(shunXuHe)\n",
    "        print(niXuHe)\n",
    "        result=[]\n",
    "        for i in range(n-1):\n",
    "            temp=abs(shunXuHe[i]//(i+1)-niXuHe[i+1]//(n-i-1))\n",
    "            result.append(temp)\n",
    "        result.append(shunXuHe[-1]//n)\n",
    "        print(result)\n",
    "        return result.index(min(result))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        pre=[0]*(n+1)\n",
    "        suf=[0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            pre[i]=pre[i-1]+nums[i-1]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            suf[i]=suf[i+1]+nums[i+1]\n",
    "        ans=inf\n",
    "        for i in range(n):\n",
    "            if i==n-1:\n",
    "                res=pre[i+1]//(i+1)\n",
    "            else:\n",
    "                res=abs(pre[i+1]//(i+1)-suf[i]//(n-i-1))\n",
    "            if ans>res:\n",
    "                ans=res\n",
    "                index=i\n",
    "        return index\n",
    "\n",
    "\n",
    "        min_value=min(ans)\n",
    "        return date.index(min_value)\n",
    "'''\n",
    "        n = len(nums)\n",
    "        pre = [0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            pre[i] = pre[i-1]+nums[i-1] # pre[1] = 0\n",
    "        suf = [0]*(n+1)\n",
    "        for i in range(n-2,-1,-1):\n",
    "            suf[i]= suf[i+1]+nums[i+1]\n",
    "        ans = inf\n",
    "        index = None\n",
    "        for i in range(n):\n",
    "            \n",
    "            if i ==n-1:\n",
    "                res = pre[i+1]//(i+1)\n",
    "            else:\n",
    "                res = abs(pre[i+1]//(i+1) - suf[i]//(n-i-1))\n",
    "            if ans > res:\n",
    "                ans = res\n",
    "                index = i\n",
    "        return index\n",
    "\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        prefixSum = [nums[0]] * len(nums)\n",
    "        suffixSum = [nums[-1]] * len(nums)\n",
    "        for i in range(1, len(nums)):\n",
    "            prefixSum[i] = prefixSum[i-1] + nums[i]\n",
    "        for j in range(len(nums)-2, -1, -1):\n",
    "            suffixSum[j] = suffixSum[j+1] + nums[j]\n",
    "\n",
    "        minPos, minVal = 0, float(\"inf\")\n",
    "        for i in range(len(nums)):\n",
    "            if i == len(nums) - 1:\n",
    "                absVal = abs(prefixSum[i]//(i+1))\n",
    "            else:\n",
    "                absVal = abs(prefixSum[i]//(i+1) - suffixSum[i+1]//(len(nums)-i-1))\n",
    "            if absVal < minVal:\n",
    "                minVal = absVal\n",
    "                minPos = i\n",
    "        return minPos"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        len_nums = len(nums)\n",
    "        pre = 0\n",
    "        pre_sum = [0] * len_nums\n",
    "        for i in range(len_nums):\n",
    "            pre += nums[i]\n",
    "            pre_sum[i] = pre\n",
    "\n",
    "        suf = 0\n",
    "        suf_sum = [0] * len_nums\n",
    "        for i in range(len_nums - 1, -1, -1):\n",
    "            suf_sum[i] = suf\n",
    "            suf += nums[i]\n",
    "\n",
    "        min_value = sys.maxsize\n",
    "        min_idx = len_nums\n",
    "        for i in range(len_nums):\n",
    "            if i == len_nums - 1:\n",
    "                av_diff = abs(pre_sum[i] // (i + 1))\n",
    "            else:\n",
    "                av_diff = abs(pre_sum[i] // (i + 1) - suf_sum[i] // (len_nums - i - 1))\n",
    "\n",
    "            if av_diff < min_value:\n",
    "                min_value = av_diff\n",
    "                min_idx = i\n",
    "\n",
    "        return min_idx\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pre = [0] * (n + 1) \n",
    "        suf = [0] * (n + 1)\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            pre[i] = pre[i - 1] + nums[i - 1]\n",
    "        # print(pre)\n",
    "        for i in range(n-2,-1,-1):\n",
    "            suf[i] = suf[i + 1] + nums[i + 1]\n",
    "        # print(stf)\n",
    "\n",
    "        ans = inf\n",
    "        index = None\n",
    "        for i in range(n):\n",
    "            if i == n - 1:\n",
    "                res = pre[i+1] // (i+1)\n",
    "            else:\n",
    "                res = abs(pre[i+1] // (i+1) - suf[i] // (n-i-1))\n",
    "            if ans > res:\n",
    "                ans = res \n",
    "                index = i \n",
    "        return index\n",
    "        \n",
    "        # return "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        prefix_sum = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            prefix_sum[i] = prefix_sum[i - 1] + nums[i - 1]\n",
    "        postfix_sum = [0] * (n + 1)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            postfix_sum[i] = postfix_sum[i + 1] + nums[i]\n",
    "        \n",
    "        # nums:[2,5,3,9,5,3]\n",
    "        # prefix_sum:[0,2,7,10,19,24,27]\n",
    "        # postfix_sum:[27,25,20,17,8,3,0]\n",
    "        \n",
    "        diff = inf\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            avg_left = prefix_sum[i + 1] // (i + 1)\n",
    "            avg_right = postfix_sum[i + 1] // (n - i - 1) if (n - i - 1) != 0 else 0\n",
    "            if abs(avg_left - avg_right) < diff:\n",
    "                diff = abs(avg_left - avg_right)\n",
    "                if diff == 0:\n",
    "                    return i\n",
    "                res = i\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        prel = list(accumulate(nums))\n",
    "        prer = list(accumulate(nums[::-1]))[::-1]\n",
    "        prel = [prel[i] // (i + 1) for i in range(n)]\n",
    "        prer = [prer[i] // (n - i) for i in range(n)]\n",
    "        res = abs(prel[0] - prer[1])\n",
    "        ans = 0\n",
    "        for i in range(n - 1):\n",
    "            if abs(prel[i] - prer[i + 1]) < res:\n",
    "                res = abs(prel[i] - prer[i + 1])\n",
    "                ans = i\n",
    "        if abs(prel[n - 1]) < res:\n",
    "            ans = n - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumAverageDifference(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        left = [0] * n\n",
    "        right = [0] * n\n",
    "        left[0] = nums[0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            left[i] = left[i - 1] + nums[i]\n",
    "        right[n - 1] = nums[n - 1]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            right[i] = right[i + 1] + nums[i]\n",
    "        right = right[1:]\n",
    "\n",
    "        out = float('inf')\n",
    "        index = 0\n",
    "        for i in range(n):\n",
    "            avg_left = left[i] // (i + 1)\n",
    "            avg_right = right[i] // (n - i - 1) if i < n - 1 else 0\n",
    "            tmp = abs(avg_left - avg_right)\n",
    "            if tmp < out:\n",
    "                out = tmp\n",
    "                index = i\n",
    "        return index\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
